#include <cstdio>

int main( )
{
    int n, ans, p, q;
    while ( scanf("%d", &n) != EOF )
    {
        if ( n == 1 ) { puts("1"); continue; }
        if ( n == 2 ) { puts("2"); continue; }
        ans = 1;
        if ( n % 3 == 1 )
        {
            ans = 4;
            n -= 4;
        }
        else
            if ( n % 3 == 2 )
            {
                ans = 2;
                n -= 2;
            }
        n /= 3;
        q = p = 1;
        while ( p <= n ) p <<= 1;
        p >>= 1;
        while ( p )
        {
            q = q * q % 2009;
            if ( p & n ) q = q * 3 % 2009;
            p >>= 1;
        }
        ans = ans * q % 2009;
        printf("%d\n", ans);
    }
    return 0;
}
